#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back
#define vec vector<int>
#define bst bitset<155>

int read(){int x = 0,sgn = 1;char ch = getchar();for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);return x*sgn;}

const int N = 155;
const ll inf = 0x3f3f3f3f3f3f3f3f;

int n,m;
int lim[N];

struct edge{int u,v,d;}e[N];
bool operator < (edge a,edge b){return a.d < b.d;}

struct mat{
	bst arr[N];
	mat(){for(int i = 1;i <= n;i++) arr[i].reset();}
	bst& operator [](int x){return arr[x];}
	const bst & operator [](int x) const {return arr[x];}
	friend bst operator * (bst a,mat b){
		bst c; for(int i = 1;i <= n;i++) c[i] = (a & b[i]).any();
		return c;
	}
	friend mat operator * (mat a,mat b){
		mat c;
		for(int i = 1;i <= n;i++)
			for(int j = 1;j <= n;j++)
				if(a[i][j])
					c[i] |= b[j];
		return c;
	}
}c;

bst v;
ll d[N],ans = inf;

bst qp(mat a,bst b,int t){
	for(;t;t >>= 1,a = a * a) if(t & 1) b = b * a;
	return b;
}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in; m = in;
	for(int i = 1;i <= m;i++) e[i].u = in,e[i].v = in,e[i].d = in;
	sort(e + 1,e + m + 1); v[1] = 1;
	for(int i = 1;i <= m;i++){
		if(e[i].d >= ans) break;
		v = qp(c,v,e[i].d - e[i - 1].d); c[e[i].v][e[i].u] = 1; // cerr<<c[e[i].u][e[i].v]<<".."<<endl;
		queue<int> q;
		for(int j = 1;j <= n;j++) if(v[j]) d[j] = 0,q.push(j);else d[j] = inf;
		while(q.size()){
			int x = q.front(); q.pop();
			for(int k = 1;k <= n;k++) if(c[k][x] && d[k] == inf) d[k] = d[x] + 1,q.push(k);
		}
		ans = min(ans,e[i].d + d[n]);
	}
	if(ans < inf) printf("%lld\n",ans);
	else puts("Impossible");
	return 0;
}
